package main

import "fmt"
//给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
//注意：答案中不可以包含重复的三元组
//给定数组 nums = [-1, 0, 1, 2, -1, -4]，
//满足要求的三元组集合为：
//[
//  [-1, 0, 1],
//  [-1, -1, 2]
//]
//nums := []int{-1, 0, 1, 2, -1, -4}

func quicksort(arr []int, left, right int){
	if left >= right{
		return
	}

	i, j := left, right
	key := arr[i]
	for i < j{
		for ;i < j; j--{
			if arr[j] < key{
				break
			}
		}
		arr[i] = arr[j]

		for ; i < j; i++{
			if arr[i] > key{
				break
			}
		}
		arr[j] = arr[i]
	}
	arr[i] = key
	quicksort(arr, left, i)
	quicksort(arr, i+1, right)
}

func threenumssum(nums []int, target int){
	res := [][]int{}
	quicksort(nums, 0, len(nums) -1)
	for k, v := range nums{
		i, j := k+1, len(nums) -1
		for i <j{
			if i == k{
				i++
				continue
			}
			if j == k{
				j--
				continue
			}

			sum := v + nums[i] + nums[j]
			if sum < target{
				i++
			}else if sum > target{
				j--
			}else{
				res = append(res, []int{v, nums[i], nums[j]})
				break
			}
		}
	}
	fmt.Println(res)
}

func main(){
	threenumssum([]int{-1, 0, 1, 2, -1, -4}, 0)
}